package leetcode.Hot100;

import leetcode.array.combine;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * https://leetcode-cn.com/problems/permutations/
 * @version 1.0
 * @date 2021/11/18 16:30
 * @see combine 注意比较着两题的 深度优先遍历，permute 是全排列，combine 是全组合。
 * 字节面试题 BAT面试题
 */
public class permute {

    // 这题可以使用深度优先遍历，也可以实现广度优先遍历。这里给出深度优先遍历的思路。
    // 深度优先遍历——回溯算法，设计一个dfs 方法，该方法需要对nums 进行全排列。在进行全排列的过程中，上一次选过的元素不能再被选择，
    // 所以需要记录数组元素的使用情况。
    static List<List<Integer>> resultList = new ArrayList<>();

    public static void main(String[] args) {
        permute(new int[]{1, 2, 3});
        permute1(new int[]{1, 2, 3});
    }

    // 全排列的个数 等于 nums.length! （数组长度的阶乘）
    // 容器 list 放 nums[i] 的全排列， nums[i+1] 的全排列是 将所有的 nums[i]的全排列的每一个 元素拿出来，在元素的缝隙 中插入 i+1
    // nums[1] list = [1]
    // nums[2] list = [1,2] [2,1]
    // nums[3] list = [3,1,2] [1,3,2] [1,2,3]  [3,2,1] [2,3,1] [2,1,3]
    static List<List<Integer>> permute(int[] nums) {
        // dp定义：result 表示全排列的结果。LinkedList 便于插入元素
        LinkedList<List<Integer>> result = new LinkedList<>();
        // dp 初始化
        if (nums.length >= 1) {
            LinkedList<Integer> first = new LinkedList<>();
            first.add(nums[0]);
            result.add(first);
        }
        int k = 1;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            LinkedList<Integer> poll = (LinkedList<Integer>) result.poll();
            while (poll.size() == k) {
                for (int j = 0; j <= poll.size(); j++) {
                    LinkedList<Integer> nextList = new LinkedList<>(poll);
                    nextList.add(j, num);
                    result.add(nextList);
                }
                if (result.peek().size() > k) {
                    break;
                } else {
                    poll = (LinkedList<Integer>) result.poll();
                }
            }
            k++;
        }
        return result;
    }

    static List<List<Integer>> permute1(int[] nums) {
        int length = nums.length;
        if (length != 0) {
            boolean[] used = new boolean[length];
            backTrack(nums, used, new LinkedList<>(), 0, length);
        }
        return resultList;
    }
    //   1,     2,     3
    // 2,  3  1,  3  1,  2
    // 3   2  3   1  2   1
    static void backTrack(int[] nums, boolean[] used, LinkedList<Integer> path, int depth, int length) {
        if (depth == length) {
            resultList.add(new ArrayList<>(path));
            return;
        } else {
            for (int i = 0; i < nums.length; i++) {
                // 该位置已经被使用，因为每次循环都是从0开始，所以必须知道本次递归前的那些递归用了哪些数组元素
                if (used[i]) continue;
                used[i] = true;
                path.addLast(nums[i]);
                backTrack(nums, used, path, depth + 1, length);
                // 重点理解这里：回溯的过程中，递归之前做了什么操作，本次递归完成后需要做对应的逆向操作。
                // 看这里 dfs(nums, used, path, depth + 1, length); 的上下四行代码，是不是很舒服，就像以这行代码为分割线，上下轴对称
                path.removeLast();
                used[i] = false;
            }
        }
    }

}
